#
# @lc app=leetcode.cn id=301 lang=python3
#
# [301] 删除无效的括号
#

# @lc code=start
class Solution:
    def removeInvalidParentheses(self, s:str) -> List[str]:
        def isValid(s:str)->bool:
            cnt = 0
            for c in s:
                if c == "(": cnt += 1
                elif c == ")": cnt -= 1
                if cnt < 0: return False  # 只用中途cnt出现了负值，你就要终止循环，已经出现非法字符了
            return cnt == 0

        # BFS
        level = {s}  # 用set避免重复
        while True:
            valid = list(filter(isValid, level))  # 所有合法字符都筛选出来
            # print(f'valid:{valid}')
            if valid: 
                return valid # 如果当前valid是非空的，说明已经有合法的产生了
            # 下一层level
            # print(f'level:{level}')  
            next_level = set()
            # next_level_ = set()
            for item in level:
                # print(item)
                for i in range(len(item)):
                    if item[i] in "()":                     # 如果item[i]这个char是个括号就删了，如果不是括号就留着
                        next_level.add(item[:i]+item[i+1:])
                        # next_level_.add(item[:i]+str(i)+item[i+1:])
                    # print(i, item[i], next_level)
                    # print(i, item[i], next_level_)
            level = next_level

# @lc code=end

